МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
КУРСОВА РОБОТА
з дисципліни: “Паралельні та розподілені обчислення”
на тему:
“Паралельне виконання операцій множення матриць
на кільцевій структурі”
Варіант № 1
Львів – 2011
ЗМІСТ
Вступ
5
1. Теоретичний розділ
6
2. Проектування граф-схеми виконання алгоритму
10
3. Розробка функціональної схеми
12
4. Розрахунковий розділ
13
5. Розробка програми
17
Висновки
19
Література
Додаток. Лістинг програми
Результати роботи програми
ВСТУП
На сьогоднішній день найбільш перспективні дві основні технології, які мають багато спільного: паралельні та розподілені обчислення.
У паралельних обчисленнях бере участь обладнання, що знаходиться, як правило, в одному фізичному місці, вони тісно поєднані між собою і всі параметри їх роботи відомі програмісту. У розподілених обчисленнях немає тісного постійного зв'язку між вузлами, вони розподілені по деякій території і параметри роботи цієї системи динамічні і не завжди відомі.
Існують різні методи і технології паралельних і розподілених обчислень, постійне зростання використання яких в сучасній практичній діяльності можна пояснити наступними обставинами:
• надзвичайно швидке зростання складності об'єктів моделювання (перехід від простих до складних ("великим") системам);
• перехід до вирішення завдань, вирішення яких вимагає досліджень, які необхідні для проведення ретельного аналізу складної поведінки ;
• необхідність управління складними промисловими і технологічними завданнями в режимі реального часу і в умовах невизначеності;
• зростання кількості завдань, для вирішення яких необхідно обробляти гігантські обсяги інформації.
Домінуюче положення при розробці паралельних програм для паралельних систем займає стандарт MPI (англ. Message Passing Interface). Програма, розроблена в моделі передачі повідомлень, може бути представлена інформаційним графом, вершинам якого відповідають паралельні гілки програми, а ребрам комунікаційні зв'язки між ними. Це можна використовувати для диспетчеризації завдань та їх обчислювальних потоків. Враховуючи гетерогенність обчислювальних ресурсів і середовищ передачі даних у кластері, можна здійснити розподіл обчислювальних потоків (гілок) з обчислювальних вузлів так, щоб мінімізувати накладні витрати на обмін даними між потоками і вирівняти обчислювальне навантаження між вузлами.
1. ТЕОРЕТИЧНИЙ РОЗДІЛ
Завдання множення матриць є базовою макрооперацією для багатьох задач лінійної алгебри. Тому ефективний паралельний алгоритм множення матриць дозволяє значно збільшити розмірність подібних завдань без збільшення часу їх вирішення. Нехай дано дві матриці, і., результат яких необхідно обчислити. Елементи результуючої матриці визначаються за формулою
Час виконання послідовного алгоритму визначається так. Нехай - час, що витрачається на множення двох чисел, - час додавання двох чисел. Час, що витрачається на обчислення одного елемента результуючої матриці. В результуючій матриці міститься елементи, тому загальний час виконання множення матриць буде рівний:
Позначимо . Звідси випливає, що. . Розглянемо паралельний алгоритм множення матриць і оцінимо час його роботи. Нехай є процесорів, причому, , де - ціле. Розпаралелимо обчислення так, щоб кожен процесор обчислював елементів результуючої матриці. Тоді сумарний час виконання можна оцінити таким чином:
Позначимо . Порівнюючи і , отримаємо : . Маємо, що час, який витрачається на множення матриць за допомогою паралельного алгоритму, в раз менший, ніж при використанні послідовного.
Розглянемо один із способів розпаралелювання алгоритму. Пронумеруємо елементи результуючої матриці за наступним правилом (нумерація елементів, а також рядків і стовпців в даному випадку ведеться з нуля):
Обчислення розподілимо так, щоб перший процесор обчислював перших елементів результуючої матриці, другий – наступні й т.д. Таким чином, кін...
